package linkList

import "fmt"

type ListNode struct {
	next  *ListNode
	value interface{}
}

type LinkedList struct {
	head   *ListNode
	length uint
}

func NewListNode(val interface{}) *ListNode {
	return &ListNode{nil, val}
}

func (this *ListNode) GetNext() *ListNode {
	return this.next
}

func (this *ListNode) GetValue() interface{} {
	return this.value
}

func NewLinkedList() *LinkedList {
	return &LinkedList{NewListNode(0), 0} // 第一个为保护节点
}

func NewLinkedListError() *LinkedList {
	fmt.Println("NewLinkedListError")
	panic("NewLinkedListError。。。。。。")
	// return &LinkedList{NewListNode(0), 0} // 第一个为保护节点
}

func (this *LinkedList) Print() {
	cur := this.head.next
	ans := ""
	for cur != nil {
		if ans == "" {
			ans = fmt.Sprintf("%v", cur.value)
		} else {
			ans = fmt.Sprintf("%v -> %v", ans, cur.value)
		}
		cur = cur.next
	}
	fmt.Println(ans)
}

// 时间复杂度 O(1)
func (this *LinkedList) InsertAfter(p *ListNode, v interface{}) (bool, *ListNode) {
	if p == nil {
		return false, nil
	}
	newNode := NewListNode(v)
	newNode.next = p.next
	p.next = newNode

	this.length++
	return true, newNode
}

// 时间复杂度 O(n)
func (this *LinkedList) InsertBefore(p *ListNode, v interface{}) (bool, *ListNode) {
	if p == nil || p == this.head { // 不能插入比保护节点还前
		return false, nil
	}
	var prev *ListNode
	cur := this.head

	for cur != nil {
		if cur == p {
			newNode := NewListNode(v)
			newNode.next = cur
			if prev != nil { // 避免插入是第一个情况
				prev.next = newNode
			}
			this.length++
			return true, newNode
		}
		prev = cur
		cur = cur.next
	}
	return false, nil
}

func (this *LinkedList) Insert2Head(v interface{}) (bool, *ListNode) {
	return this.InsertBefore(this.head.next, v)
}

func (this *LinkedList) Insert2Tail(v interface{}) (bool, *ListNode) {
	cur := this.head
	for cur.next != nil {
		cur = cur.next
	}
	return this.InsertAfter(cur, v)
}

func (this *LinkedList) FindIndex(index uint) *ListNode {
	if index >= this.length {
		return nil
	}
	cur := this.head
	for i := 0; i <= int(index); i++ {
		cur = cur.next
	}
	return cur
}

func (this *LinkedList) DeleteNode(p *ListNode) bool {
	if p == nil {
		return false
	}
	prev := this.head
	cur := this.head.next
	for cur.next != nil {
		if cur == p {
			prev.next = cur.next
			return true
		}
		prev = cur
		cur = cur.next
	}
	return false
}
